#include <iostream>
#include <string>
#include <iomanip>
#include <fstream>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;

// 图书信息结构体
struct Book {
	string id;	  // ISBN
	string name;  // 书名
	double price; // 定价
};
typedef Book ElemType;

// 链表节点结构体
struct LNode {
	ElemType data; // 数据域
	LNode *next;   // 指针域
};
typedef LNode *LinkList;

// 算法2.6 单链表的初始化
Status InitList_L(LinkList &L) {
	// 构造一个空的单链表L
	L = new LNode;	// 生成新结点作为头结点，用头指针L指向头结点
	L->next = NULL; // 头结点的指针域置空
	L->data.price = 0; // 使用头结点的price字段存储链表长度
	return OK;
}

//销毁
Status DestroyList_L(LinkList &L)
{
	LinkList p;
	while(L)
	{
		p=L;  
		L=L->next;
		delete p;  
	}
	return OK;
}


Status ClearList(LinkList & L) {
	// 将L重置为空表
	LinkList p, q;
	p = L->next; //p指向第一个结点
	while (p) {    //没到表尾
		q = p->next;
		delete p;
		p = q;
	}
	L->next = NULL; //头结点指针域为空
	L->data.price = 0;
	return OK;
}

//求表长
int  ListLength_L(LinkList L) {
//返回L中数据元素个数
	LinkList p;
	p = L->next; //p指向第一个结点
	int i = 0;
	while (p) { //遍历单链表,统计结点数
		i++;
		p = p->next;
	}
	return i;
}

//判断表是否为空
int ListEmpty(LinkList L) {
	//若L为空表，则返回1，否则返回0
	if (L->next)  //非空
		return 0;
	else
		return 1;
}

// 算法2.7 单链表的取值
Status GetElem_L(LinkList L, int i, ElemType &e) {
	LNode *p = L->next;
	int j = 1;
	while (p && j < i) {
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return ERROR;
	e = p->data;
	return OK;
}

// 算法2.8 按值查找
LNode *LocateElem_L(LinkList L, double price) {
	LNode *p = L->next;
	while (p && p->data.price != price) {
		p = p->next;
	}
	return p;
}

// 算法2.9 单链表的插入
Status ListInsert_L(LinkList &L, int i, ElemType &e) {
	LNode *p = L;
	int j = 0;
	while (p && j < i - 1) {
		p = p->next;
		++j;
	}
	if (!p || j > i - 1)
		return ERROR;
	LNode *s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	L->data.price++; // 增加链表长度
	return OK;
}

// 算法2.10 单链表的删除
Status ListDelete_L(LinkList &L, int i) {
	LNode *p = L;
	int j = 0;
	while (p->next && j < i - 1) {
		p = p->next;
		++j;
	}
	if (!(p->next) || j > i - 1)
		return ERROR;
	LNode *q = p->next;
	p->next = q->next;
	delete q;
	L->data.price--; // 减少链表长度
	return OK;
}

// 算法2.11 前插法创建单链表
void CreateList_F(LinkList &L, int n) {
	L = new LNode;
	L->next = NULL;
	L->data.price = 0; // 初始化链表长度为0

	ifstream file("book.txt");
	if (!file) {
		cout << "未找到相关文件，无法打开！" << endl;
		exit(ERROR);
	}

	string head_1, head_2, head_3;
	file >> head_1 >> head_2 >> head_3;

	while (file.good()) {
		LNode *p = new LNode;
		file >> p->data.id >> p->data.name >> p->data.price;
		p->next = L->next;
		L->next = p;
		L->data.price++; // 增加链表长度
	}
	file.close();
}

// 算法2.12 后插法创建单链表
void CreateList_L(LinkList &L, int n) {
	L = new LNode;
	L->next = NULL;
	L->data.price = 0; // 初始化链表长度为0
	LNode *r = L;

	ifstream file("book.txt");
	if (!file) {
		cout << "未找到相关文件，无法打开！" << endl;
		exit(ERROR);
	}

	string head_1, head_2, head_3;
	file >> head_1 >> head_2 >> head_3;

	while (file.good()) {
		LNode *p = new LNode;
		file >> p->data.id >> p->data.name >> p->data.price;
		p->next = NULL;
		r->next = p;
		r = p;
		L->data.price++; // 增加链表长度
	}
	file.close();
}

int main() {
    LinkList L;
    ElemType book;
    int position;
    double price;

    // 测试初始化链表
    cout << "测试初始化链表：" << endl;
    if (InitList_L(L)) {
        cout << "链表初始化成功" << endl;
    } else {
        cout << "链表初始化失败" << endl;
    }

    // 测试后插法创建链表
    cout << "\n测试后插法创建链表：" << endl;
    CreateList_L(L, 0);
    cout << "链表创建完成，当前链表长度：" << L->data.price << endl;

    // 测试判断链表是否为空
    cout << "\n测试判断链表是否为空：" << endl;
    if (ListEmpty(L)) {
        cout << "链表为空" << endl;
    } else {
        cout << "链表不为空" << endl;
    }

    // 测试获取链表长度
    cout << "\n测试获取链表长度：" << endl;
    cout << "链表长度：" << ListLength_L(L) << endl;

    // 测试取值
    cout << "\n测试取值：" << endl;
    position = 2;
    if (GetElem_L(L, position, book)) {
        cout << "第" << position << "个位置的图书信息：" << book.id << " " << book.name << " " << book.price << endl;
    } else {
        cout << "获取第" << position << "个位置的图书信息失败" << endl;
    }

    // 测试按值查找
    cout << "\n测试按值查找：" << endl;
    price = 50.0;
    LNode *result = LocateElem_L(L, price);
    if (result) {
        cout << "找到价格为" << price << "的图书：" << result->data.name << endl;
    } else {
        cout << "未找到价格为" << price << "的图书" << endl;
    }

    // 测试插入
    cout << "\n测试插入：" << endl;
    position = 3;
    book = {"9787302257646", "数据结构", 35.0};
    if (ListInsert_L(L, position, book)) {
        cout << "在第" << position << "个位置插入成功" << endl;
    } else {
        cout << "在第" << position << "个位置插入失败" << endl;
    }

    // 测试删除
    cout << "\n测试删除：" << endl;
    position = 2;
    if (ListDelete_L(L, position)) {
        cout << "删除第" << position << "个位置的元素成功" << endl;
    } else {
        cout << "删除第" << position << "个位置的元素失败" << endl;
    }

    // 输出当前链表内容
    cout << "\n当前链表内容：" << endl;
    for (LNode *p = L->next; p; p = p->next) {
        cout << p->data.id << " " << p->data.name << " " << p->data.price << endl;
    }

    // 测试清空链表
    cout << "\n测试清空链表：" << endl;
    if (ClearList(L)) {
        cout << "清空链表成功" << endl;
    } else {
        cout << "清空链表失败" << endl;
    }

    // 测试销毁链表
    cout << "\n测试销毁链表：" << endl;
    if (DestroyList_L(L)) {
        cout << "销毁链表成功" << endl;
    } else {
        cout << "销毁链表失败" << endl;
    }

    return 0;
}
